package demo1;

import java.util.*;

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        Map<String, Integer> h1 = new HashMap<>();
        for(String x : words){
            h1.put(x, h1.getOrDefault(x, 0) + 1);
        }
        int n = words.length, m = words[0].length();

        for(int i = 0; i < m; i++){
            Map<String, Integer> h2 = new HashMap<>();
            for(int left = i, right = i, count = 0; right + m <= s.length(); right += m){
                String in = s.substring(right, right + m);
                h2.put(in, h2.getOrDefault(in, 0) + 1);
                if(h2.get(in) <= h1.getOrDefault(in, 0)) { count++;}

                if(right - left + 1 > n * m){
                    String out = s.substring(left, left + m);
                    if(h2.get(out) <= h1.getOrDefault(out, 0)){
                        count--;
                    }
                    h2.put(out, h2.get(out) - 1);
                    left += m;
                }

                if(count == n){
                    list.add(left);
                }
            }
        }
        return list;
    }

    public List<Integer> findAnagrams(String s, String p) {
        char[] s1 = s.toCharArray();
        char[] s2 = p.toCharArray();
        int[] h1 = new int[26];
        int[] h2 = new int[26];
        for(int i = 0; i < p.length(); i++){
            h2[s2[i] - 'a']++;
        }

        List<Integer> list = new ArrayList<>();
        int n = s.length(), m = p.length(), t = 0;
        for(int left = 0, right = 0; right < n; right++){
            char in = s1[right];
            h1[in - 'a']++;
            if(h1[in - 'a'] <= h2[in - 'a']){
                t++;
            }

            while(right - left + 1 > m){
                char out = s1[left];
                if(h1[out - 'a'] <= h2[out - 'a']){
                    t--;
                }
                h1[out - 'a']--;
                left++;
            }

            if(t == m){
                list.add(left);
            }
        }
        return list;
    }

    public String minWindow(String s, String t) {
        int begin = -1, len = Integer.MAX_VALUE, count = 0;
        int n = s.length(), m = t.length();
        int[] h1 = new int[128];
        for(int i = 0; i < m; i++){
            h1[t.charAt(i)]++;
        }

        int[] h2 = new int[128];
        for(int left = 0, right = 0; right < n; right++){
            char in= s.charAt(right);
            h2[in]++;
            if(h2[in] <= h1[in]) { count++;}

            while(count == m){
                if(right - left + 1 < len){
                    begin = left;
                    len = right - left + 1;
                }

                char out = s.charAt(left);
                if(h2[out] <= h1[out]) { count--;}
                h2[out]--;
                left++;
            }
        }

        if(begin == -1){
            return "";
        }else{
            return s.substring(begin, begin + len);
        }
    }
}
